package 力扣._7006_销售利润最大化;

import java.util.*;

public class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        //dp[i] = max(dp[i-1], dp[offer.start-1] + coin)
        //区间选择，将offer按照结束位置分类
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        for (List<Integer> offer : offers) {
            List<List<Integer>> list = map.getOrDefault(offer.get(1), new LinkedList<>());
            list.add(offer);
            map.put(offer.get(1), list);

        }
        int[] dp = new int[n + 1];

        //dp[i]
        for (int i = 0; i <= n; i++) {
            if (i > 0)
                dp[i] = dp[i - 1];  // 不卖当前区间
            List<List<Integer>> lists = map.get(i);
            if (lists == null)
                continue;
            for (List<Integer> list : lists) {
                int start = list.get(0);
                int coins = list.get(2);
                if (start > 0)
                    dp[i] = Math.max(dp[i], dp[start - 1] + coins);
                else
                    dp[i] = Math.max(dp[i], coins);
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        List<List<Integer>> offers = new LinkedList<>();
        List<Integer> list1 = new LinkedList<>();
        list1.add(0);
        list1.add(1);
        list1.add(4);
        List<Integer> list2 = new LinkedList<>();
        list2.add(0);
        list2.add(0);
        list2.add(9);
        List<Integer> list3 = new LinkedList<>();
        list3.add(0);
        list3.add(0);
        list3.add(9);
        offers.add(list1);
        offers.add(list2);
        offers.add(list3);
        int i = new Solution().maximizeTheProfit(5, offers);
        System.out.println(i);
    }
}
